# 查找
# ls = ["赵","钱","孙","李","周","吴","郑","王"]
# def x(lst,key):
#     for i in lst:
#         if i == key:
#             return "找到了"
#     return "没找到"
# print(x(ls,"赵"))
# ls = [1,3,5,7,9,13,15,17,19,35,37,39,57,59,79]
from itertools import count


def search1(ls,key):
    if ls ==[]:
        return "没找到"
    # 找到中间下标
    mid = len(ls)//2
    print("下标",mid,ls[mid])
    # 根据中间下标对应的值和key判断
    if ls[mid] == key:
        # print("---找到了-------")
        k = ls.count(key)
        print(k)
        #  中间值=key  找到了
        return "找到了"
    #  中间值>key  往前找 改变列表，重新调用search1（）
    elif ls[mid] > key:
        return search1(ls[0:mid:],key)
    #  中间值<key  往后找 改变列表
    else:
        return search1(ls[mid+1::], key)
ls = [1, 3,3,3, 5, 7, 9, 13,13,13, 15, 17, 19, 19,19,35, 37, 39, 57, 59, 79]
print(search1(ls,13))